package leetcode.medium.limit50;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @author yaoyao1.liu@zhaopin.com.cn
 * @since 2022-11-09 14:14
 **/
public class No47 {

    public static void main(String[] args) {

        No47 no47 = new No47();
        List<List<Integer>> permute = no47.permute(new int[]{1, 1, 2});
        System.out.println(permute);
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int length = nums.length;
        if (length == 0) {
            return result;
        }
        boolean[] used = new boolean[length];
        deal(result, 0, length, nums, new ArrayList<>(), used);
        return result;
    }

    public void deal(List<List<Integer>> result, int index, int length, int[] nums, List<Integer> one, boolean[] used) {
        if (index == length) {
            if (!checkExist(result, one, length)) {
                result.add(new ArrayList<>(one));
            }
            return;
        }
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (!used[i]) {
                one.add(num);
                used[i] = true;
                deal(result, index + 1, length, nums, one, used);
                used[i] = false;
                one.remove(one.size() - 1);
            }
        }
    }

    public boolean checkExist(List<List<Integer>> result, List<Integer> one, int length) {
        for (List<Integer> list : result) {
            boolean flag = true;
            for (int i = 0; i < length; i++) {
                Integer integer = list.get(i);
                Integer integer1 = one.get(i);
                flag = flag && (Objects.equals(integer, integer1));
            }
            if (flag) {
                return true;
            }
        }
        return false;
    }
}
